﻿// 201 欧拉函数.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/21/problem/489

输入T，一共T组数据，每组一个数n，输出它的欧拉函数φ(n)。

输入格式
第一行一个数字T。

接下来T行，每行一个数字n。

输出格式
一共T行，每行一个数，表示这个数的欧拉函数φ(n)。

输入样例
2
12345
987654321
输出样例
6576
619703040
数据规模
对于100%
的数据，保证1≤T≤103,1≤n≤109。
*/
#include <iostream>
#include <vector>

using namespace std;

int T;
int n;


void solve() {
	cin >> n;
	if (n == 1) {
		cout << 1 << endl;
		return;
	}
	int cn = n;
	vector<int> primes;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			primes.push_back(i);
			while (n % i == 0) n /= i;
		}
	}
	if (n != 1) primes.push_back(n);

	long long ret = cn;
	for (int i = 0; i < primes.size(); i++) {
		ret /= primes[i];
		ret *= primes[i] - 1;
	}
	cout << ret << endl;
	return;
}

int main()
{
	cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

 